package util

type FpTree struct {
	Root *treeNode
}

// ResultTreeNode 结果字典数节点
type ResultTreeNode struct {
	Val      string //节点值
	Count    int
	IsFinal  bool       //是否为叶子节点
	End      [][]string //叶子结点的全部组合
	EndCount []int
	Next     []*ResultTreeNode //指针域
}

// treeNode FP-Tree 节点
type treeNode struct {
	val      string               //值
	count    int                  //计数
	parent   *treeNode            //父节点
	children map[string]*treeNode //子节点映射
	brother  *treeNode            //兄弟节点
}

// ArInfo 单条数据
type ArInfo struct {
	Arr   []string
	Count int
}

// FpTreeTask 建树任务
type FpTreeTask struct {
	resTree *ResultTreeNode //对应字典树节点
	ArrData []*ArInfo       //数据
}

//getL 二进制掩码求单一path的全部组合
func (f *FpTree) getL() ([][]string, []int) {
	var allS = make([]string, 0, 8)
	var allC = make([]int, 0, 8)
	var now *treeNode
	for now = f.Root; len(now.children) != 0; {
		for key, v := range now.children {
			allS = append(allS, key)
			allC = append(allC, v.count)
			now = v
		}

	}
	var res = make([][]string, 0, 8)
	var count = make([]int, 0, 8)
	var m = 1 << len(allS)
	for i := 1; i < m; i++ {
		var tem = make([]string, 0, 8)
		var minC = 100000
		for ind, j := 0, 1; j <= i; j <<= 1 {
			if j&i != 0 {
				tem = append(tem, allS[ind])
				minC = min(minC, allC[ind])
			}
			ind++
		}
		res = append(res, tem)
		count = append(count, minC)

	}
	return res, count
}

//IsFinal 判断是否是单一路径
func (f *FpTree) IsFinal() bool {
	for now := f.Root; true; {
		var l = len(now.children)
		if l == 0 {
			break
		}
		if l > 1 {
			return false
		}
		for _, val := range now.children {
			now = val
		}
	}
	return true
}

type stack struct {
	dat  []string
	sTop int
}

//ToArray dfs遍历结果字典树获取结果
func (r *ResultTreeNode) ToArray() [][]*ItemsAndCount {
	var res = make([][]*ItemsAndCount, 0, 1<<4)
	var re = &res
	var stack = &stack{
		dat: make([]string, 128),
	}
	for _, v := range r.Next {
		_dfs(v, re, stack)
	}

	return res

}
func _dfs(r *ResultTreeNode, res *[][]*ItemsAndCount, stack *stack) {

	stack.dat[stack.sTop] = r.Val

	stack.sTop++

	if r.IsFinal {
		t := make([]string, stack.sTop-1)
		copy(t, stack.dat[:stack.sTop-1])
		for ind, v := range r.End {
			v = append(v, t...)
			var l = len(v)
			for len(*res) < l {
				*res = append(*res, make([]*ItemsAndCount, 0, 8))
			}
			(*res)[l-1] = append((*res)[l-1], &ItemsAndCount{
				Items: v,
				Count: r.EndCount[ind],
			})
		}
	} else {
		t := make([]string, stack.sTop)
		copy(t, stack.dat[:stack.sTop])
		var l = len(t)
		for len(*res) < l {
			*res = append(*res, make([]*ItemsAndCount, 0, 8))
		}
		(*res)[l-1] = append((*res)[l-1], &ItemsAndCount{
			Items: t,
			Count: r.Count,
		})
		for _, v := range r.Next {
			_dfs(v, res, stack)
		}
	}
	stack.sTop--
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}
